2 万字 10 图带你⼿撕 STL 关联

式容器源码⼤家好，我是⼩贺。

⽂章每周持续更新，可以微信搜索公众号「herongwei」第⼀时间阅读和催更。

本⽂ GitHub : https://github.com/rongweihe/CPPNotes已经收录，有⼀线⼤⼚⾯试点思维导图，也整理了很多我的⽂档，欢迎点个⼩和完善。⼀起加油，变得更⭐好！

鸽了好久的 STL 源码系列，这周开始更新，还剩最后两篇，分别是关联式容器和 STL 基本算法。

距离上篇源码剖析的⽂章好像在⼏个⽉前？

咕咕咕，连我⾃⼰都看不下去了，怎么能这么懒呢？正好趁着这⼏天休假，⼀⿎作⽓的把该写的⽂章补上吧。

16.1 前⾔

STL 源码剖析系列已经出了三篇：

5 千字⻓⽂+ 30 张图解 | 陪你⼿撕 STL 空间配置器源码万字⻓⽂炸裂！⼿撕 STL 迭代器源码与 traits 编程技法超硬核 | 2 万字+20 图带你⼿撕 STL 序列式容器源码上⼀篇，我们剖析了序列式容器，这⼀篇我们来学习下关联式容器。

在 STL 编程中，容器是我们经常会⽤到的⼀种数据结构，容器分为序列式容器和关联式容器。

两者的本质区别在于：序列式容器是通过元素在容器中的位置顺序存储和访问元素，⽽关联容器则是通过键 (key) 存储和读取元素。

本篇着重剖析关联式容器相关背后的知识点，来⼀张思维导图。

16.2 容器分类

前⾯提到了，根据元素存储⽅式的不同，容器可分为序列式和关联式，那具体的⼜有哪些分类呢，这⾥我画了⼀张图来看⼀下。

关联式容器⽐序列式容器更好理解，从底层实现来分的话，可以分为 RB_tree 还是hash_table，所有暴露给⽤户使⽤的关联式容器都绕不过底层这两种实现。

不多 BB。我们先来分析其底层的两种实现，后⾯在逐个⼀⼀剖析其外在形式，这样对于新⼿还是⽼⼿，对于其背后核⼼的设计和奥秘，理解起来都会丝滑顺畅。

16.3 RB-tree 介绍与应⽤

⾸先来介绍红⿊树，RB Tree 全称是 Red-Black Tree，⼜称为“红⿊树”，它⼀种特殊的⼆叉查找树。红⿊树的每个节点上都有存储位表示节点的颜⾊，可以是红 (Red) 或⿊ (Black)。

红⿊树的特性:

每个节点或者是⿊⾊，或者是红⾊。

根节点是⿊⾊。

每个叶⼦节点（NIL）是⿊⾊。 [注意：这⾥叶⼦节点，是指为空(NIL或NULL)的叶⼦节点！]如果⼀个节点是红⾊的，则它的⼦节点必须是⿊⾊的。

从⼀个节点到该节点的⼦孙节点的所有路径上包含相同数⽬的⿊节点。

注意：

特性 (3)中的叶⼦节点，是只为空(NIL或null)的节点。

特性 (5)确保没有⼀条路径会⽐其他路径⻓出俩倍。因⽽，红⿊树是相对是接近衡的⼆叉树。

红⿊树示意图如下：

红⿊树保证了最坏情形下在O(logn)时间复杂度内完成查找、插⼊及删除操作；效率⾮常之⾼。

因此红⿊树可⽤于很多场景，⽐如下图。

好了，红⿊树介绍到这⾥差不多了，关于红⿊树的分析在深⼊⼜是另⼀篇⽂章了，下⾯我们在简单介绍⼀下红⿊树的两种数据操作⽅式。

16.4 RB-tree 的基本操作

红⿊树的基本操作包括添加、删除。

在对红⿊树进⾏添加或删除之后，都会⽤到旋转⽅法。原因在于添加或删除红⿊树中的节点之后，红⿊树就发⽣了变化，可能不满⾜红⿊树的 5 条性质，也就说不再是⼀颗红⿊树了，⽽是⼀颗普通的树。

⽽通过旋转，可以使这颗树重新成为红⿊树。简单点说，旋转的⽬的是让树保持红⿊树的特性。

在红⿊树⾥的旋转包括两种：左旋和右旋。

左旋：对节点 X 进⾏左旋，也就说让节点 X 成为左节点。

右旋：对节点 X 进⾏右旋，也就说让节点 X 成为右节点。

说完了旋转，我们再来看⼀下它的插⼊，有两种插⼊⽅式：

//不允许键值重复插⼊

pair<iterator, bool> insert_unique(const value_type& x);

//允许键值重复插⼊

iterator insert_equal(const value_type& x);

RB-tree ⾥⾯分两种插⼊⽅式，⼀种是允许键值重复插⼊，⼀种不允许。可以简单的理解，如果调⽤ insert_unique 插⼊重复的元素，在 RB-tree ⾥⾯其实是⽆效的。

其实在 RB-tree 源码⾥⾯，上⾯两个函数⾛到最底层，调⽤的是同⼀个 __insert() 函数。

知道了数据的操作⽅式，我们再来看 RB-tree 的构造⽅式：内部调⽤ rb_tree_node_allocator，每次恰恰配置⼀个节点，会调⽤ simple_alloc 空间配置器来配置节点。

并且分别调⽤四个节点函数来进⾏初始化和构造化。

get_node(), put_node(), create_node(), clone_node(), destroy_node();RB-tree 的构造⽅式也有两种：⼀种是以现有的 RB-tree 复制⼀个新的 RB-tree，另⼀种是产⽣⼀棵空的树。

16.5 哈希表（hashtable）介绍和应⽤

红⿊树的介绍就到这⾥了，下⾯我们来看⼀下哈希表。

我们知道数组的特点是：寻址容易，插⼊和删除困难；⽽链表的特点是：寻址困难，插⼊和删除容易。

那么我们能不能综合两者的特性，做出⼀种寻址容易，插⼊删除也容易的数据结构？

答案是肯定的，这就是哈希表。

哈希表，也被称为散列表，是⼀种常⽤的数据结构，这种结构在插⼊、删除、查找等操作上也具有”常数平均时间“的表现。

也可以视为⼀种字典结构。

在讲具体的 hashtable 源码之前，我们先来认识两个概念：

散列函数：使⽤某种映射函数，将⼤数映射为⼩数。负责将某⼀个元素映射为⼀个”⼤⼩可接受内的索引“，这样的函数称为 hash function（散列函数）。

使⽤散列函数可能会带来问题：可能会有不同的元素被映射到相同的位置，这⽆法避免，因为元素个数有可能⼤于分配的 array 容量，这就是所谓的碰撞问题，解决碰撞问题⼀般有：线性探测、⼆次探测、开链等。

不同的⽅法有不同的效率差别，本⽂以 SGI STL 源码⾥采⽤的开链法来进⾏ hashtable 的学习。

拉链法，可以理解为“链表的数组”，其思路是：如果多个关键字映射到了哈希表的同⼀个位置处，则将这些关键字记录在同⼀个线性链表中，如果有重复的，就顺序拉在这条链表的后⾯。

注意，bucket 维护的链表，并不采⽤ STL 的 list ，⽽是⾃⼰维护的 hash table node，⾄于buckets 表格，则是以 vector 构造完成，以便具有动态扩充能⼒。

hash table 的定义：

//模板参数定义

/*

Value：节点的实值类型Key：节点的键值类型HashFcn： hash function的类型ExtractKey：从节点中取出键值的⽅法（函数或仿函数）EqualKey：判断键值是否相同的⽅法（函数或仿函数）Alloc：空间配置器

*/

//hash table的线性表是⽤ vector 容器维护

template <class_Val, class_Key, class_HashFcn,
class_ExtractKey, class_EqualKey, class_Alloc>
classhashtable {
public:
typedef _Key key_type;
typedef _Val value_type;
typedef _HashFcn hasher;
typedef _EqualKey key_equal;
typedefsize_t            size_type;
typedefptrdiff_t         difference_type;
typedef value_type*       pointer;
typedefconst value_type* const_pointer;
typedef value_type&       reference;
typedefconst value_type& const_reference;
hasher hash_funct() const { return _M_hash; }
key_equal key_eq() const { return _M_equals; }
private:
typedef _Hashtable_node<_Val> _Node;

这⾥需要注意的是，hashtable 的迭代器是正向迭代器，且必须维持这整个 buckets vector 的关系，并记录⽬前所指的节点。其前进操作是⽬前所指的节点，前进⼀个位置。

//以下是hash table的成员变量

private:
hasher                _M_hash;
key_equal             _M_equals;
_ExtractKey           _M_get_key;

vector<_Node*,_Alloc> _M_buckets;//⽤vector维护bucketssize_type _M_num_elements;//hashtable中list节点个数

public:
typedef
_Hashtable_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>
iterator;
typedef
_Hashtable_const_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,
_Alloc>
const_iterator;
public:

//构造函数

hashtable(size_type __n,
const _HashFcn&    __hf,
const _EqualKey&   __eql,
const _ExtractKey& __ext,
const allocator_type& __a = allocator_type())
: __HASH_ALLOC_INIT(__a)
_M_hash(__hf),
_M_equals(__eql),
_M_get_key(__ext),
_M_buckets(__a),
_M_num_elements(0)
{

_M_initialize_buckets(__n);//预留空间,并将其初始化为空0//预留空间⼤⼩为⼤于n的最⼩素数

}

提供两种插⼊元素的⽅法：insert_equal允许重复插⼊；insert_unique不允许重复插⼊。

//插⼊元素节点,不允许存在重复元素

pair<iterator, bool> insert_unique(const value_type& __obj) {

//判断容量是否够⽤, 否则就重新配置

resize(_M_num_elements + 1);

//插⼊元素,不允许存在重复元素

return insert_unique_noresize(__obj);
}

//插⼊元素节点,允许存在重复元素

iterator insert_equal(const value_type& __obj)

{//判断容量是否够⽤, 否则就重新配置

resize(_M_num_elements + 1);

//插⼊元素,允许存在重复元素

return insert_equal_noresize(__obj);
}

16.6 hashtable 的基本操作

后⾯⻢上要介绍的关联容器 set、multiset、map 和 multimap 的底层机制都是基于 RB-Tree红⿊树，虽然能够实现在插⼊、删除和搜素操作能够达到对数平均时间，可是要求输⼊数据有⾜够的随机性。

⽽ hash table 不需要要求输⼊数据具有随机性，在插⼊、删除和搜素操作都能达到常数平均时间。

SGI 中实现 hash table 的⽅式，是在每个 buckets 表格元素中维护⼀个链表, 然后在链表上执⾏元素的插⼊、搜寻、删除等操作，该表格中的每个元素被称为桶 (bucket)。

虽然开链法并不要求表格⼤⼩为质数，但 SGI STL 仍然已质数来设计表格⼤⼩，并且将 28 个质数计算好，以备随时访问。

// Note: assumes long is at least 32 bits.

// 注意：假设long⾄少为32-bits, 可以根据⾃⼰需要修改//定义28个素数⽤作hashtable的⼤⼩

enum { __stl_num_primes = 28 };
staticconstunsignedlong __stl_prime_list[__stl_num_primes] = {
53ul,         97ul,         193ul,       389ul,       769ul,
1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};

//返回⼤于n的最⼩素数

inlineunsignedlong__stl_next_prime(unsignedlong __n) {
constunsignedlong* __first = __stl_prime_list;
constunsignedlong* __last = __stl_prime_list +
(int)__stl_num_primes;
constunsignedlong* pos = lower_bound(__first, __last, __n);

hashtable的节点配置和释放分别由 new_node 和 delete_node 来完成，并且插⼊操作和表格重整分别由 insert_unique 和 insert_equal ,resize 三个函数来完成。限于篇幅，这⾥⽤三张图来展示：

C++ STL 标准库中，不仅是 unordered_xxx 容器，所有⽆序容器的底层实现都采⽤的是哈希表存储结构。更准确地说，是⽤“链地址法”（⼜称“开链法”）解决数据存储位置发⽣冲突的哈希表，整个存储结构如图所示。

其中，Pi 表示存储的各个键值对。

最左边的绿⾊称之为 bucket 桶，可以看到，当使⽤⽆序容器存储键值对时，会先申请⼀整块连续的存储空间，但此空间并不⽤来直接存储键值对，⽽是存储各个链表的头指针，各键值对真正的存储位置是各个链表的节点。

在 C++ STL 标准库中，将图 1 中的各个链表称为桶（bucket），每个桶都有⾃⼰的编号（从0 开始）。当有新键值对存储到⽆序容器中时，整个存储过程分为如下⼏步：

将该键值对中键的值带⼊设计好的哈希函数，会得到⼀个哈希值（⼀个整数，⽤ H 表示）；

将 H 和⽆序容器拥有桶的数量 n 做整除运算（即 H % n），该结果即表示应将此键值对存储到的桶的编号；

建⽴⼀个新节点存储此键值对，同时将该节点链接到相应编号的桶上。

另外值得⼀提的是，哈希表存储结构还有⼀个重要的属性，称为负载因⼦（load factor）。

该属性同样适⽤于⽆序容器，⽤于衡量容器存储键值对的空/满程序，即负载因⼦越⼤，意味着容器越满，即各链表中挂载着越多的键值对，这⽆疑会降低容器查找⽬标键值对的效率；反之，负载因⼦越⼩，容器肯定越空，但并不⼀定各个链表中挂载的键值对就越少。

举个例⼦，如果设计的哈希函数不合理，使得各个键值对的键带⼊该函数得到的哈希值始终相同（所有键值对始终存储在同⼀链表上）。这种情况下，即便增加桶数是的负载因⼦减⼩，该容器的查找效率依旧很差。

⽆序容器中，负载因⼦的计算⽅法为：

负载因⼦ = 容器存储的总键值对 / 桶数默认情况下，⽆序容器的最⼤负载因⼦为 1.0。如果操作⽆序容器过程中，使得最⼤复杂因⼦超过了默认值，则容器会⾃动增加桶数，并重新进⾏哈希，以此来减⼩负载因⼦的值。

需要注意的是，此过程会导致容器迭代器失效，但指向单个键值对的引⽤或者指针仍然有效。

这也就解释了，为什么我们在操作⽆序容器过程中，键值对的存储顺序有时会“莫名”的发⽣变动。

C++ STL 标准库为了⽅便⽤户更好地管控⽆序容器底层使⽤的哈希表存储结构，各个⽆序容器的模板类中都提供表所示的成员⽅法。

成员⽅法功能bucket_count()返回当前容器底层存储键值对时，使⽤桶的数量max_bucket_count()返回当前系统中，unordered_xxx 容器底层最多可以使⽤多少个桶bucket_size(n)返回第 n 个桶中存储键值对的数量bucket(key)返回以 key 为键的键值对所在桶的编号load_factor()返回 unordered_map 容器中当前的负载因⼦max_load_factor()返回或者设置当前 unordered_map 容器的最⼤负载因⼦rehash(n)尝试重新调整桶的数量为等于或⼤于 n 的值。如果 n ⼤于当前容器使⽤的桶数，则该⽅法会是容器重新哈希，该容器新的桶数将等于或⼤于 n。反之，如果 n 的值⼩于当前容器使⽤的桶数，则调⽤此⽅法可能没有任何作⽤。

reserve(n)将容器使⽤的桶数（bucket_count() ⽅法的返回值）设置为最适合存储 n 个元素的桶hash_function()返回当前容器使⽤的哈希函数对象介绍到这⾥，hashtable 的源码的⼤观也差不多了，想深⼊研究源码等细节⼤家可以访问开头的GitHub链接。

下⾯开始讲解具体的关联式容器，这⾥的分类⽐较多，有的读者可能会有点分不清。

那么⼩贺也给⼤家总结了⼀句话：只要是前缀带了unordered的就是⽆序，后缀带了multi的就是允许键重复，插⼊采⽤ insert_equal ⽽不是 insert_unique。

16.7 set、multiset、unordered_set、

unordered_multiset有了前⾯的 RB_tree 做铺垫，下⾯来学习 set/multiset 和 map/multimap 就容易多了。

先来看⼀下 set 的性质set 以 RB-tree 作为其底层机制，所有元素都会根据元素的键值⾃动被排序。

set 的元素就是键值，set 不允许两个元素有相同的键值。

不允许通过 set 的迭代器来改变 set 的元素值，因为 set 的元素值就是键值，更改了元素值就会影响其排列规则，如果任意更改元素值，会严重破坏 set 组织，因此在定义 set 的迭代器时被定义成了 RB-tree 的 const_iterator。

由于 set 不允许有两个相同的键值，所以插⼊时采⽤的是 RB-tree 的 insert_unique ⽅式这⾥的类型的定义要注意⼀点, 都是 const 类型, 因为 set 的主键定义后就不能被修改了,所以这⾥都是以const类型。

下⾯来看⼀下 set 的源码set 的主要实现⼤都是调⽤ RB-tree 的接⼝，这⾥的类型的定义要注意⼀点, 都是 const 类型，因为 set 的主键定义后就不能被修改了，所以这⾥都是以 const 类型。

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <classKey, classCompare = less<Key>, classAlloc = alloc>
#else
template <classKey, classCompare, classAlloc = alloc>
#endif
classset {
public:
// typedefs:
typedef Key key_type;
typedef Key value_type;
typedef Compare key_compare;
typedef Compare value_compare;
private:

// ⼀RB-tree为接⼝封装

typedef rb_tree<key_type, value_type, identity<value_type>,
key_compare, Alloc> rep_type;
rep_type t;  // red-black tree representing set
public:

// 定义的类型都是const类型, 不能修改

typedeftypename rep_type::const_pointer pointer;
typedeftypename rep_type::const_pointer const_pointer;
typedeftypename rep_type::const_reference reference;
typedeftypename rep_type::const_reference const_reference;
typedeftypename rep_type::const_iterator iterator;
typedeftypename rep_type::const_iterator const_iterator;
typedeftypename rep_type::const_reverse_iterator reverse_iterator;
typedeftypename rep_type::const_reverse_iterator
const_reverse_iterator;
typedeftypename rep_type::size_type size_type;
typedeftypename rep_type::difference_type difference_type;
...
};

构造函数构造成员的时候调⽤的是 RB-tree 的 insert_unique。

classset {
public:
...
set() : t(Compare()) {}

explicit set(const Compare& comp) : t(comp) {} // 不能隐式转换// 接受两个迭代器// 构造函数构造成员的时候调⽤的是RB-tree的insert_unique

template <classInputIterator>
set(InputIterator first, InputIterator last)
: t(Compare()) { t.insert_unique(first, last); }
template <classInputIterator>
set(InputIterator first, InputIterator last, const Compare& comp)
: t(comp) { t.insert_unique(first, last); }
set(const value_type* first, const value_type* last)
: t(Compare()) { t.insert_unique(first, last); }
set(const value_type* first, const value_type* last, const Compare&
comp)
: t(comp) { t.insert_unique(first, last); }
set(const_iterator first, const_iterator last)
: t(Compare()) { t.insert_unique(first, last); }
set(const_iterator first, const_iterator last, const Compare& comp)
: t(comp) { t.insert_unique(first, last); }
...
};

成员属性获取

classset {
public:
...

// 所有的操作都是通过调⽤RB-tree获取的

key_compare key_comp() const { return t.key_comp(); }
value_compare value_comp() const { return t.key_comp(); }
iterator begin() const { return t.begin(); }
iterator end() const { return t.end(); }
reverse_iterator rbegin() const { return t.rbegin(); }
reverse_iterator rend() const { return t.rend(); }
bool empty() const { return t.empty(); }
size_type size() const { return t.size(); }
size_type max_size() const { return t.max_size(); }

// 交换

void swap(set<Key, Compare, Alloc>& x) { t.swap(x.t); }

// 其他的find, count等都是直接调⽤的RB-tree的接⼝

iterator find(const key_type& x) const { return t.find(x); }
size_type count(const key_type& x) const { return t.count(x); }
iterator lower_bound(const key_type& x) const {
return t.lower_bound(x);
}
iterator upper_bound(const key_type& x) const {
return t.upper_bound(x);
}
pair<iterator,iterator> equal_range(const key_type& x) const {
return t.equal_range(x);
}
...
};

insert 操作源码

classset {
public:
...

// pair类型我们准备下⼀节分析, 这⾥是直接调⽤insert_unique, 返回插⼊成功就是pair( , true), 插⼊失败则是( , false)

typedef  pair<iterator, bool> pair_iterator_bool;
pair<iterator,bool> insert(const value_type& x) {
pair<typename rep_type::iterator, bool> p = t.insert_unique(x);
return pair<iterator, bool>(p.first, p.second);
}

// 指定位置的插⼊

iterator insert(iterator position, const value_type& x) {
typedeftypename rep_type::iterator rep_iterator;
return t.insert_unique((rep_iterator&)position, x);
}

// 可接受范围插⼊

template <classInputIterator>
void insert(InputIterator first, InputIterator last) {
t.insert_unique(first, last);
}
...
};

erase 的实现是通过调⽤ RB-tree 实现的 erase。

classset {
public:
...

// erase的实现是通过调⽤RB-tree实现的erase

void erase(iterator position) {
typedeftypename rep_type::iterator rep_iterator;
t.erase((rep_iterator&)position);
}
size_type erase(const key_type& x) {
return t.erase(x);
}
void erase(iterator first, iterator last) {
typedeftypename rep_type::iterator rep_iterator;
t.erase((rep_iterator&)first, (rep_iterator&)last);
}
void clear() { t.clear(); }
...
};

最后剩下⼀个重载运算符，也是以 RB-tree 为接⼝调⽤。

到这⾥，set ⼤部分的源码都已经过了⼀遍。

multiset 与 set 特性完全相同，唯⼀差别在于它允许键值重复，因此插⼊操作采⽤的是底层机制 RB-tree 的 insert_equal() ⽽⾮ insert_unique()。

接下来我们来了解⼀下两个新的数据结构：hash_set 与 unordered_set。

它们都属于基于哈希表(hash table)构建的数据结构，并且是关键字与键值相等的关联容器。

那 hash_set 与 unordered_set 哪个更好呢？实际上 unordered_set 在C++11的时候被引⼊标准库了，⽽ hash_set 并没有，所以建议还是使⽤ unordered_set ⽐较好，这就好⽐⼀个是官⽅认证的，⼀个是⺠间流传的。

在 SGI STL 源码剖析⾥，是以 hash_set 剖析的。

hash_set 将哈希表的接⼝在进⾏了⼀次封装, 实现与 set 类似的功能.

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <classValue, classHashFcn = hash<Value>,
classEqualKey = equal_to<Value>,
classAlloc = alloc>
#else
template <classValue, classHashFcn, classEqualKey, classAlloc =
alloc>
#endif
classhash_set {
private:

// 定义hashtable

typedef hashtable<Value, Value, HashFcn, identity<Value>,  EqualKey,
Alloc> ht;
ht rep;
public:
typedeftypename ht::key_type key_type;
typedeftypename ht::value_type value_type;
typedeftypename ht::hasher hasher;
typedeftypename ht::key_equal key_equal;

// 定义为const类型, 键值不允许修改

typedeftypename ht::size_type size_type;
typedeftypename ht::difference_type difference_type;
typedeftypename ht::const_pointer pointer;
typedeftypename ht::const_pointer const_pointer;
typedeftypename ht::const_reference reference;
typedeftypename ht::const_reference const_reference;

// 定义迭代器

typedeftypename ht::const_iterator iterator;
typedeftypename ht::const_iterator const_iterator;

// 仿函数

hasher hash_funct() const { return rep.hash_funct(); }
key_equal key_eq() const { return rep.key_eq(); }
...
};

构造函数

classhash_set
{
...
public:

hash_set() : rep(100, hasher(), key_equal()) {} // 默认构造函数, 表⼤⼩默认为100最近的素数

explicit hash_set(size_type n) : rep(n, hasher(), key_equal()) {}
hash_set(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {}
hash_set(size_type n, const hasher& hf, const key_equal& eql)
: rep(n, hf, eql) {}
#ifdef __STL_MEMBER_TEMPLATES
template <classInputIterator>
hash_set(InputIterator f, InputIterator l)
: rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); }
template <classInputIterator>
hash_set(InputIterator f, InputIterator l, size_type n)
: rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); }
template <classInputIterator>
hash_set(InputIterator f, InputIterator l, size_type n,
const hasher& hf)
: rep(n, hf, key_equal()) { rep.insert_unique(f, l); }
template <classInputIterator>
hash_set(InputIterator f, InputIterator l, size_type n,
const hasher& hf, const key_equal& eql)
: rep(n, hf, eql) { rep.insert_unique(f, l); }
...
};

插⼊删除等操作insert调⽤的是insert_unqiue函数

classhash_set
{
...
public:

// 都是调⽤hashtable的接⼝, 这⾥insert_unqiue函数

pair<iterator, bool> insert(const value_type& obj)
{
pair<typename ht::iterator, bool> p = rep.insert_unique(obj);
return pair<iterator, bool>(p.first, p.second);
}

set、multiset、unordered_set、unordered_multiset 总结性质setmultisetunordered_setunordered_multiset底层实现红⿊树红⿊树哈希表哈希表键值重复不允许允许不允许允许插⼊元素insert_uniqueinsert_equalinsert_uniqueinsert_equal元素有序有序有序⽆序⽆序是否⽀持[]运算符不⽀持不⽀持不⽀持不⽀持迭代器性质const_iteratorconst_iteratorconst_iteratorconst_iterator

16.8 map、multimap、unordered_map、

unordered_multimap在分析 map 之前，我们来分析⼀下 pair 这种结构。

pair 是⼀个有两个变量的结构体, 即谁都可以直接调⽤它的变量, 毕竟 struct 默认权限都是public, 将两个变量⽤ pair 绑定在⼀起, 这就为 map<T1, T2> 提供的存储的基础.

template <classT1, classT2> // 两个参数类型

structpair {
typedef T1 first_type;
typedef T2 second_type;

// 定义的两个变量

T1 first;
T2 second;

// 构造函数

pair() : first(T1()), second(T2()) {}
pair(const T1& a, const T2& b) : first(a), second(b) {}
#ifdef __STL_MEMBER_TEMPLATES
template <classU1, classU2>
pair(const pair<U1, U2>& p) : first(p.first), second(p.second) {}
#endif
};

重载实现：

template <classT1, classT2>
inlinebooloperator==(const pair<T1, T2>& x, const pair<T1, T2>& y) {
return x.first == y.first && x.second == y.second;
}
template <classT1, classT2>
inlinebooloperator<(const pair<T1, T2>& x, const pair<T1, T2>& y) {
return x.first < y.first || (!(y.first < x.first) && x.second <
y.second);
}

整体 pair 的功能与实现都是很简单的，这都是为 map 的实现做准备的，接下来我们就来分析map 的实现。

map 基本结构定义

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <classKey, classT, classCompare = less<Key>, classAlloc =
alloc>
#else
template <classKey, classT, classCompare, classAlloc = alloc>
#endif
classmap {
public:

typedef Key key_type; // 定义键值typedef T data_type; // 定义数据

typedef T mapped_type;

typedef pair<const Key, T> value_type; // 这⾥定义了map的数据类型为pair,且键值为const类型, 不能修改

typedef Compare key_compare;
private:
typedef rb_tree<key_type, value_type,
select1st<value_type>, key_compare, Alloc> rep_type;

// 定义红⿊树, map是以rb-tree结构为基础的

rep_type t;  // red-black tree representing map
public:
...

构造函数：map 所有插⼊操作都是调⽤的 RB-tree 的 insert_unique，不允许出现重复的键。

classmap {
public:
...
public:
// allocation/deallocation

map() : t(Compare()) {} // 默认构造函数

explicit map(const Compare& comp) : t(comp) {}
#ifdef __STL_MEMBER_TEMPLATES

// 接受两个迭代器

template <classInputIterator>
map(InputIterator first, InputIterator last)
: t(Compare()) { t.insert_unique(first, last); }
template <classInputIterator>
map(InputIterator first, InputIterator last, const Compare& comp)
: t(comp) { t.insert_unique(first, last); }
...

基本属性的获取

classmap {
public:
...
public:

// 实际调⽤的是RB-tree的key_comp函数

key_compare key_comp() const { return t.key_comp(); }

// value_comp实际返回的是⼀个仿函数value_compare

value_compare value_comp() const { return value_compare(t.key_comp());
}

// 以下的begin, end等操作都是调⽤的是RB-tree的接⼝

iterator begin() { return t.begin(); }
const_iterator begin() const { return t.begin(); }
iterator end() { return t.end(); }
const_iterator end() const { return t.end(); }
reverse_iterator rbegin() { return t.rbegin(); }
const_reverse_iterator rbegin() const { return t.rbegin(); }
reverse_iterator rend() { return t.rend(); }
const_reverse_iterator rend() const { return t.rend(); }
bool empty() const { return t.empty(); }
size_type size() const { return t.size(); }
size_type max_size() const { return t.max_size(); }

// 交换, 调⽤RB-tree的swap, 实际只交换head和count

void swap(map<Key, T, Compare, Alloc>& x) { t.swap(x.t); }
...
};
template <classKey, classT, classCompare, classAlloc>
inlinevoidswap(map<Key, T, Compare, Alloc>& x,
map<Key, T, Compare, Alloc>& y) {
x.swap(y);
}

重载的分析

classmap {
public:
...
public:
T& operator[](const key_type& k) {
return (*((insert(value_type(k, T()))).first)).second;
}
...
};

insert(value_type(k, T()) : 查找是否存在该键值, 如果存在则返回该pair, 不存在这重新构造⼀该键值并且值为空*((insert(value_type(k, T()))).first) : pair的第⼀个元素表示指向该元素的迭代器, 第⼆个元素指的是(false与true)是否存在, first 便是取出该迭代器⽽ * 取出pair.

(*((insert(value_type(k, T()))).first)).second : 取出pair结构中的second保存的数据

这⾥有坑，初学者容易掉进去，请注意：重载 operator[]，这⼀步返回是实值 value(即pair.second)的引⽤，假如原先没有定义 map 对象，即你访问的键值 key 不存在，则会⾃动新建⼀个 map 对象，键值 key 为你访问的键值key，实值 value 为空，看下⾯的例⼦就明⽩了。

我在⾃⼰的开发机上测试，int 类型默认 value 为 0，bool 类型默认 value 为 false，string 类型默认是空。

_Tp& operator[](const key_type& __k) {
iterator __i = lower_bound(__k);
// __i->first is greater than or equivalent to __k.
if (__i == end() || key_comp()(__k, (*__i).first))
__i = insert(__i, value_type(__k, _Tp()));
return (*__i).second;

//其实简单的⽅式是直接返回

//return (*((insert(value_type(k, T()))).first)).second;
}

map 的其他 insert， erase， find 都是直接调⽤ RB-tree 的接⼝函数实现的，这⾥就不直接做分析了。

16.9 map、 multimap、unordered_map、

unordered_multimap 总结map 和 multimap 的共同点：

两者底层实现均为红⿊树，不可以通过迭代器修改元素的键，但是可以修改元素的值；

拥有和 list 某些相同的特性，进⾏元素的新增和删除后，操做前的迭代器依然可⽤；

不同点：

map 键不能重复，⽀持 [] 运算符；

multimap ⽀持重复的键，不⽀持 [] 运算符；

map 并不像 set ⼀样将 iterator 设为 RB-tree 的 const_iterator，因为它允许⽤户通过其迭代器修改元素的实值。

map 和 unordered_map 共同点：

两者均不能有重复的建，均⽀持[]运算符不同点：

map 底层实现为红⿊树unordered_map 底层实现为哈希表unordered_map 是不允许存在相同的键存在，底层调⽤的 insert_unique() 插⼊元素unordered_multimap 可以允许存在多个相同的键，底层调⽤的 insert_equal() 插⼊元素map 并不像 set ⼀样将 iterator 设为 RB-tree 的 const_iterator，因为它允许⽤户通过其迭代器修改元素的实值。

性质mapmultimapunordered_mapunordered_multimap底层实现红⿊树红⿊树哈希表哈希表键值重复不允许允许不允许允许插⼊元素insert_uniqueinsert_equalinsert_uniqueinsert_equal元素有序有序有序⽆序⽆序是否⽀持[]⽀持不⽀持⽀持不⽀持运算符迭代器性⾮ const_iterator⾮ const_iterator⾮ const_iterator⾮ const_iterator质是否能修不能修改key，可不能修改key，可不能修改key，可以不能修改key，可以修改元素值以修改value以修改value修改value改value

16.10 思考

为什么 std::set 不⽀持[]运算符？

对于 std::map ⽽⾔，我们看⼀个例⼦：

std::map<std::string,int> m = { {"a",1}, {"b", 2 } };

m["a"] 返回的是1所在单元的引⽤。

⽽如果对于 std::set std::string s = { "a", "b" }; ⽽⾔ s["a"] 应该是个什么类型呢？

我们⽤索引取⼀个容器的元素 a[key] = value 的前提是既有 key ⼜有 value。

set 只有 key 没有 value，加了[]会导致歧义。

参考

1、《STL 源码剖析》

2、https://github.com/FunctionDou/STL